% A RE ECRIRE. 

% GOALS : http://lsirpeople.epfl.ch/punceva/project/accessp2p.htm
%     *  Investigate new access structures designed specifically for P2P information systems. The access structure should be self-organizing, without relying on centralized servers.
%     * All operations like insert, update and search should be based on local interactions only.
%     * Provide good scalability of resources spent by a single peer in the total amount of data in the network.
%     * Provide reliability even if certain numbers of peers are off-line.
%     * Solve the problem related to constructing the structure from scratch.
%     * Balancing the efforts among the peers.
%     * Support user's autonomy.

% Reprendre intro P2PR-tree et demirbas03peer
% Mentionner PDMS 


\chapter{Introduction}

%\minitoc
%\ochap{}{} 

% \ochap{C}{ette} dissertation traite de l'indexation et de localisation d\'ecentralis\'ee de ressources dans les syst\`emes distribu\'es, dynamiques
% %\`a large \'echelle.  
% TODO
\section*{Motivation}

\ochap{L}{e} probl\`eme g\'en\'eral abord\'e dans cette dissertation est celui de la publication de ressources dans un r\'eseau ainsi que l'acc\`es \`a 
ces ressources au moyen de requ\^etes de haut niveau. Les ressources peuvent \^etre des donn\'ees, 
des services (librairies, programmes scientifiques, sites Web, etc.)
ou bien des ressources mat\'erielles (CPU, disque dur, bande passante, etc.), l'ensemble formant un syst\`eme d'information global. 
Au sein d'un tel syst\`eme, un index a la charge de mettre en relation de fa\c con transparente les fournisseurs des ressources avec les consommateurs de ressources. 

Les technologies de l'information et de la communication (TIC) occupent une place croissante dans les activit\'es humaines. 
% ----------------OU------------------
% 
% \ochap{B}{arom\`etre} de la <<  Net-\'Economie >> et de la <<  Soci\'et\'e de l'information >>, le << Global Information Technology Report  >> du 
% Forum \'economique mondial \cite{gitr} souligne chaque ann\'ee 
% la place croissante qu'occupent les technologies de l'information et de la communication (TIC) dans les activit\'es humaines. 
% 
% -------------------------------------
Cette \'evolution se traduit par un acc\`es mondialis\'e et permanent (<< anyplace, anytime >>) \`a un ensemble de ressources num\'eriques et informatiques.
Les services d'acc\`es \`a ces diff\'erentes ressources reposent sur des infrastructures de r\'eseaux et peuvent \^etre qualifi\'es de \emph{services en r\'eseau}.
Dans cette th\`ese, nous nous int\'eressons plus particuli\`erement aux services en r\'eseau dont la gestion des donn\'ees s'effectue {in situ} (<< in-network
data storage >>). 
Dans ce type d'application, les donn\'ees sont g\'en\'er\'ees par des n\oe uds du r\'eseau et sont stock\'ees dans des n\oe uds du r\'eseau, et non 
dans un syst\`eme de stockage traditionnel, de type base de donn\'ees, centre de traitement de donn\'ees ou autre. 
Le caract\`ere centralis\'e de ces solutions de gestion de donn\'ees traditionnelles peut en effet les rendre inappropri\'ees dans certains cas : contraintes de co\^ut, 
passage \`a l'\'echelle avec contraintes de latence, 
connectivit\'e du r\'eseau fluctuante, contraintes de confidentialit\'e entra\^inant une volont\'e de contr\^ole local sur les donn\'ees, 
nature d\'ecentralis\'ee de l'application incompatible avec un contr\^ole centralis\'e,
etc. 
Parmi les applications requ\'erant une gestion des donn\'ees dans leur << habitat naturel >>, selon l'expression employ\'ee dans \cite{huebsch03querying}, on trouve 
les plateformes d'\'echange de fichiers ou les r\'eseaux de capteurs. 
% Des exemples repr\'esentatifs de tels services sont les plateformes d'\'echange de fichiers
% %et les syt\`emes pervasifs.
% ou les r\'eseaux de senseurs. 
Les plateformes d'\'echange de fichiers mettent en relation une communaut\'e de particuliers dont chacun met \`a disposition une partie de son disque dur 
afin de partager les fichiers qu'elle contient (audio, vid\'eo ou autre). 
% Quant aux syst\`emes pervasifs, aussi appel\'es ambiants ou ubiquitaires, 
% ils constituent un paradigme r\'ecent en informatique distribu\'ee d\'ecrivant un grand nombre de petits dispositifs \'electroniques bon march\'e interconnect\'es et int\'egr\'es
% \`a l'environnement de l'utilisateur, afin de l'aider dans ses t\^aches. 
Quant aux r\'eseaux de capteurs, ce sont des r\'eseaux \emph{ad hoc} sans fil dont les micro-capteurs, d\'eploy\'es dans une zone g\'eographique, 
sont capables de collecter et transmettre des donn\'ees environnementales de mani\`ere autonome. 
Un micro-capteur int\`egre outre l'unit\'e de captage, une unit\'e de traitement informatique et de stockage des donn\'ees. 


% Dans le cadre d'une gestion des donn\'ees \emph{in situ}, les donn\'ees et les t\^aches de gestion de ces donn\'ees sont donc distribu\'ees 
% sur un ensemble d'\'equipements ou n\oe uds de r\'eseau.  

Outre la d\'ecentralisation compl\`ete de la gestion de donn\'ees, ces exemples d'applications illustrent trois autres 
sp\'ecificit\'es ayant une incidence sur la gestion des donn\'ees. 
Une premi\`ere sp\'ecificit\'e est la \emph{dynamicit\'e} du r\'eseau : 
les participants d'une plateforme de partage de fichiers peuvent se connecter ou se d\'econnecter \`a tout moment ou
%les \'el\'ements \'electroniques d'un syst\`eme ambiant tomber en panne d'\'energie. 
un capteur tomber en panne d'\'energie, se perdre dans la nature, etc. 
Une deuxi\`eme sp\'ecificit\'e est la \emph{prise de d\'ecision en l'absence de connaissance globale} de l'\'etat du syst\`eme. 
En effet, pour des raisons de passage \`a l'\'echelle, de m\'emoire limit\'ee ou de s\'ecurit\'e, 
les n\oe uds du r\'eseau ne disposent que d'une connaissance partielle de leur environnement 
: connaissance partielle des autres participants et des fichiers qu'ils partagent dans le cas des plateformes d'\'echange ; 
connaissance partielle des autres capteurs et du contexte spatial pour les capteurs en r\'eseau.
Enfin une troisi\`eme sp\'ecificit\'e est la n\'ecessit\'e d'un \emph{passage \`a l'\'echelle incr\'emental} (<< horizontal scaling >> ou << scaling out >>).  
% Soutenue par l'augmentation constante des capacit\'es de stockage et la disponiblit\'e de CPU bon march\'es (<< commodity hardware >>), l'offre quantitative de ressources 
% accessible explose. 
Lors d'une mont\'ee en charge applicative, une solution pour pr\'eserver la disponibilit\'e du service est la mise \`a niveau du mat\'eriel sur lequel s'ex\'ecute l'application 
(<< vertical scaling >> ou << scaling up >>).
Mais cette solution de passage \`a l'\'echelle n'est pas toujours applicable, comme le montrent nos exemples : les plateformes participatives sont 
fond\'ees sur la mutualisation de ressources de particuliers, tandis que les micro-capteurs en r\'eseau sont soumis \`a des contraintes fortes en termes de taille et 
de consommation \'energ\'etique. Une alternative consiste \`a concevoir des syst\`emes sur un principe << le nombre fait la force >>, capables de s'auto-organiser pour 
f\'ed\'erer les ressources bon march\'e d'\'equipements en r\'eseau. Les performances globales de ces syst\`emes croissent en fonction du nombre de n\oe uds du r\'eseau. 
L'augmentation de la charge qu'entra\^ine l'arriv\'ee d'un nouveau participant est ainsi compens\'ee par les ressources (CPU, m\'emoire, bande passante,\ldots) qu'il apporte au syst\`eme. 
%, en termes de requ\^etes comme de donn\'ees.
%Trace la voie \`a une \'evolution des usages et des applications :  
% Enra\^ine \'emergence nouveaux usages et avec, d\'eveloppement des services en r\'eseau : applications distribu\'ees ax\'ees sur la mutualisation de ressources. 
% Il s'agit de mettre en commun des ressources dispers\'ees sur un r\'eseau, afin de les mettre \`a disposition des usagers. 
% Les ressources peuvent \^etre de tous types : fichiers multim\'edia, mat\'eriel informatique, senseurs, ... Le r\'eseau est typiquement Internet. 
%Les ressources elles-m\^emes sont souvent mise \`a disposition par des particuliers-usagers (syst\`emes P2P)
% \begin{itemize}
% %\item Web 2.0 : Publication en ligne de contenu produit par les internautes-utilisateurs (contenu multim\'edia avec plateformes comme FlickR, Youtube, MySpace ou contenu textuel avec encyclop\'edies collaboratives telle que Wikipedia http://fr.wikipedia.org))
% \item Multiplication des plateformes de partage/\'echange de fichiers. Souvent assimil\'ees \'a la technologie P2P
% \item D\'eveloppement plateformes de mutualisation ressources mat\'erielles : grid computing. Service r\'eseau unilat\'ral ou bilat\'eral. Dans dernier cas, construit \`a 
% partir de ressources appartenant \`a des particuliers (<< volunteer computing >> ou << cycle harvesting >>), ce qui rejoint 1er ex.  
% \item Nouveaux paradigmes en informatique distribu\'ee telle que informatique ambiante/pervasive :
% Communication entre entit\'es nombreuses ayant peu de ressources CPU/m\'emoire => d\'elocalisation m\'emoire et traitements) et g\'eographiquement r\'eparties
% \end{itemize}
% \vspace{0.6cm}
 % Ce sont ces applications auxquelles nos travaux sur l'indexation et la localistion s'adressent. 
% De mani\`ere g\'en\'erale, les applications pr\'esentant les besoins sp\'ecifiques suivants : 
% 
% \begin{itemize}
% %\item Applications interactives (contraintes de latence) de plus en plus massives : Passage \`a l'\'echelle massif (donn\'ees, traitements)
% \item Passage \`a l'\'echelle incr\'emental : r\'eseaux fond\'es sur principe de mutualisation ressources de particuliers, faibles bon march\'es, avec id\'ee
%  que capacti\'es globales augmentent au fur et \`a mesure arriv\'ee ressources (cas plateformes participatives)
% \item Auto-organisation : syst\`emes dynamiques, volatilit\'e des participants, pas d'administration centrale => n\'ecessit\'e minimisation intervention humaines + robustesse 
% (cas plateformes participatives)
% \item D\'ecision \`a partie de connaissances locales uniquement (cas informatique ambiante)
% \end{itemize}
% \vspace{0.6cm}
% 
% %diviser pour mieux r\'egner => distribuer les donn\'ees et les traitements, ie d\'ecentraliser. 
% Pour r\'epondre \`a ces besoins, le choix d'une architecture distribu\'ee pr\'esente de nombreux arguments.
% Parmi les raisons de distribuer un syst\`eme : 
% \begin{itemize} 
% \item Augmenter sa capacit\'e \`a moindre co\^ut, en ajoutant graduellement des ressources/n\oe uds ou en regroupant des ensembles
% de ressources/n\oe uds d\'ej\`a existants ; 
% \item Communiquer entre entit\'es distantes (t\'el\'ecommunication, r\'eseau LAN, ...) et mettre en rapport des des banques de donn\'ees r\'eparties (usagers d'Internet, etc.) ;
% \item Conserver un contr\^ole local des donn\'ees et assurer une absence de << single point of failure >>.
% \end{itemize}
%\section{Probl\'ematique g\'en\'rale d'indexation et enjeux}
% Contraintes de gestion de la dynamicit\'e, de d\'ecentralisation, de passage \`a l'\'echelle incr\'emental : un d\'efi cl\'e que doivent relever 
% les services en r\'eseaux est la conception d'\emph{index} qui soient expressifs, tout en int\'egrant leurs contraintes propres.
% Un tel index doit fournir des m\e'thodes d'acc\`es permettant, \'etant donn\'ee la description d'une donn\'ee, de la localiser efficacement
% parmi un volume important de donn\'ees h\'eberg\'ees sur diff\'erents h\^otes.  
%Contraintes de gestion de la dynamicit\'e, de d\'ecentralisation, de passage \`a l'\'echelle incr\'emental : un d\'efi cl\'e que doivent relever 
%les services en r\'eseaux est la conception d'\emph{index} qui int\'egrent leurs contraintes propres.
%Un tel index doit fournir des m\e'thodes d'acc\`es permettant, \'etant donn\'ee la description d'une donn\'ee, de la localiser efficacement
%parmi un volume important de donn\'ees h\'eberg\'ees sur diff\'erents h\^otes.  
%L'utilisation d'un index d\'ecentralis\'e qui soit hautement disponible tout en croissant continuement est ext\^ement difficile. Contruire un service en r\'eseau ou toute
%applciation au-dessus d'une brique logicielle pr\'esentant ces propri\'et\'es 


\paragraph{}L'examen des contraintes li\'ees \`a la gestion des donn\'ees \emph{in situ} dans les services en r\'eseau, soul\`eve 
un d\'efi important : \'etant donn\'e un ensemble de n\oe uds en r\'eseau ainsi qu'un ensemble de donn\'ees r\'eparties sur ces n\oe uds, \'etant donn\'e que ces
ensembles sont dynamiques et potentiellement tr\`es grands, comment localiser une donn\'ee efficacement en l'absence de connaissances globales ?  
En d'autres termes, comment concevoir un \emph{index} qui soit adapt\'e ?
%: gestion de la dynamicit\'e, architecture d\'ecentralis\'ee, passage \`a l'\'echelle incr\'emental. % efficace et expressif}. 
%Le r\^ole d'un index est de permettre l'extraction efficace de donn\'ees \`a grande \'echelle.
Typiquement, un index prend en entr\'ee un ensemble de crit\`eres, exprim\'es sous forme d'une \emph{requ\^ete}, et retourne un ensemble d'adresses : celles des n\oe uds du r\'eseau 
h\'ebergeant les ressources qui satisfont la requ\^ete. 
Un index fournit des \emph{m\'ethodes d'acc\`es}, c'est-\`a-dire les structures de donn\'ees et les algorithmes de recherche impliqu\'es dans l'indexation et
la localisation des donn\'ees. 
Nous nous int\'eressons plus pr\'ecis\'ement aux index permettant une \emph{recherche sur le contenu} : 
une ressource est localis\'ee, non pas \`a partir d'une adresse, mais \`a partir d'une description, que l'on souhaite la plus riche possible. 
En d'autres termes, nous nous int\'eressons aux index offrant un support aux donn\'ees \emph{multi-dimensionnelles} et aux requ\^etes de haut niveau sur de telles donn\'ees. 
Les souscriptions et les \'ev\'enements dans un syst\`eme de notification, les descripteurs de fichiers dans un syst\`eme d'\'echange de fichiers, 
ou les descripteurs d'images dans le domaine des images sont des exemples parmi beaucoup d'autres d'objets multi-dimensionnels. 
La recherche de donn\'ees dans un intervalle, de donn\'ees dominantes au sens de Pareto, d'inclusion ou d'englobement 
sont des exemples de requ\^etes de haut niveau sur des donn\'ees multi-dimensionnelles. La solution pr\'econis\'ee 
pour acc\'el\'erer le processus d'interrogation est l'utilisation de techniques d'indexation multi-dimensionnelles.
% Un << bon >> index doit permettre de localiser des objets efficacement, c'est-\`a-dire rapidement et avec une \'economie de moyens.
% %Pour ce faire, un index g\`ere pour chaque ressource des m\'etadonn\'ees et les correspondances entre ces m\'etadonn\'ees et les n\oe uds h\'ebergeant la ressource. 
% La conception des m\'ethodes d'acc\`es doit donc chercher \`a optimiser les recherches, en fonction des crit\`eres jug\'es pertinents dans le cadre applicatif.  
%Un tel index permet \`a un utilisateur connect\'e \`a une plateforme d'\'echange de fichiers d'acc\'eder \`a un fichier en sp\'ecifiant par exemple des mots cl\'es. 
% L'usage courant d'un index est le suivant : le client \'emet une requ\^ete d\'ecrivant des conditions sur des donn\'ees et l'index localise 
% le ou les n\oe uds du r\'eseau h\'ebergant l'ensemble des donn\'ees pertinentes pour la-dite requ\^ete. Une connexion en point \`a point est ensuite \'etablie entre
% le client et le ou les n\oe uds h\^otes. 
% Les m\'ethodes d'acc\`es recouvrent les m\'etadonn\'ees associant \`a un ensemble de description des adresses dans le r\'eseau, et les protocoles
% de routage permettant leur mise-\`a-jour et leur exploitation lors des recherches. 

La r\'ealisation, le d\'eploiement et l'exploitation d'un index multi-dimensionnel d\'ecentralis\'e, capable de s'adapter dynamiquement aux ressources disponibles tout en pr\'eservant 
la continuit\'e du service, repr\'esentent des t\^aches complexes. 
 %Une infrastructure prenant en charge cette complexit\'e est une plus-value certaine dans le d\'eveloppement de larges applications distribu\'ees.  
% Comme le prouvent les nombreuses solutions d'index dans le domaine, les \emph{overlay pair-\`a-pair} (P2P) forment une approche adapt\'ee pour
% Le paradigme pair-\`a-pair, en favorisant des architectures r\'eseaux d\'ecentralis\'ees, 
% Les nombreuses solutions d'index d\'ecentralis\'es d\'evelopp\'es d\'emontrent sur des \emph{overlay pair-\`a-pair} (P2P)  
% que constituent une infrastructure adapt\'ee pour la conception d'index . 
Comme \'evoqu\'e plus haut, les exigences d'un tel index ne sont pas satisfaites par des approches traditionnelles de gestion de donn\'ees dans les syst\`emes distribu\'es, 
telles que les bases de donn\'ees distribu\'ees. 
% On a mentionn\'e que les approches traditionnelles de gestion de donn\'ees dans les syst\`emes distribu\'es, telles que les bases de donn\'ees distribu\'ees, 
% ne conviennent pas dans le cas 
\emph{A contrario}, le \emph{paradigme pair-\`a-pair} (P2P) d\'eveloppe une approche d\'ecentralis\'ee pour le partage de ressources. 
% Il a \'et\'e largement 
% exploit\'e par ce qui est l'un des services en r\'eseau \`a l'\'echelle d'Internet le plus populaire : les plateformes de t\'el\'echargement de fichiers multim\'edia. 
Les syst\`emes P2P pr\'esentent une communaut\'e d'int\'er\^ets avec la classe d'applications cibl\'ee dans cette th\`ese. 
Ce qui explique que les probl\'ematiques consid\'er\'ees dans le cadre du P2P intersectent nos probl\'ematiques de 
gestion de la dynamicit\'e, de prise de d\'ecision d\'ecentralis\'ee et de passage \`a l'\'echelle incr\'emental. 
Les syst\`emes P2P sont des r\'eseaux d\'ecentralis\'es, dans lesquels les n\oe uds (pairs) ont des r\^oles sym\'etriques. Les pairs sont organis\'es selon 
une topologie logique, que l'on nomme \emph{overlay}. Chaque pair poss\`ede une vue partielle du r\'eseau, r\'eduite \`a ses voisins. 
En l'absence de connaissance de l'\'etat et de contr\^ole globaux, les pairs doivent le plus souvent coop\'erer avec leurs voisins pour permettre au syst\`eme
de remplir son r\^ole. 
Dans un overlay P2P impl\'ementant un index, un pair peut h\'eberger une partie des donn\'ees et/ou une partie de la structure de donn\'ees servant \`a stocker les correspondances entre 
donn\'ees et adresses physiques des n\oe uds. 
Lors de son traitement, une requ\^ete est relay\'ee de n\oe ud en n\oe ud au sein de l'overlay, jusqu'\`a avoir travers\'e l'ensemble des pairs capables de localiser 
des donn\'ees pertinentes. 
% Dans le cas d'un index bas\'e sur un overlay P2P, la connaissance des donn\'ees et de leur localit\'e est distribu\'ee sur l'ensemble des pairs. Chaque pair connair 
% L'ex\'ecution des m\'ethodes d'acc\'es
% , qui englobent la distribution des donn\'ees et le routage par contenu, se fait de mani\`ere coop\'erative entre les pairs. 
%\cite{mirrezaei07raqnet}
% De nombreux syst\`emes issus du domaine P2P sont en effet orient\'es vers la gestion de donn\'ees 
% , telles que les plateformes d\'ecentralis\'ees d'\'echange de fichiers, et se comportent essentiellement comme des index distribu\'es %%\cite{akbarinia??thesis}. 

La premi\`ere g\'en\'eration de plateformes d\'ecentralis\'ees d'\'echange de fichiers, repr\'esent\'ee par la version 0.4 de Gnutella \cite{gnutella}, 
a ouvert la voie aux solutions d'index bas\'ees sur des overlays P2P. Les overlays sur le mod\`ele de Gnutella v0.4, qualifi\'es de \emph{non-structur\'es}, 
recherchent les donn\'ees en aveugle : les requ\^etes sont propag\'ees sans distinction \`a tous les n\oe uds du r\'eseau, dans la limite d'un p\'erim\`etre donn\'e. 
Si le mod\`ele a ses avantages, il entra\^ine toutefois un gaspillage de la bande passante et n'offre aucune garantie sur l'issue des recherches, 
une donn\'ee pouvant \^etre index\'ee sans toutefois \^etre localis\'ee. 
De la volont\'e d'am\'eliorer ces points \'emerge un mod\`ele dit \emph{structur\'e}, qui propose de guider les recherches afin d'en optimiser les performances. 
%Les efforts de recherche pour am\'eliorer ces points ont conduit au mod\`ele dit \emph{structur\'e},  
%Ce mod\`ele, dit \emph{structur\'e}, am\'eliore les performances des recherches par-rapport au mod\`ele non-structur\'e. 
Pour ce faire, les n\oe uds de l'overlay sont organis\'es selon une topologie exhibant de bonnes propri\'et\'es de routage. Les informations de localisation des donn\'ees 
sont ensuite distribu\'ees sur les n\oe uds de telle fa\c con \`a permettre aux algorithmes de recherche d'exploiter ces propri\'et\'es. 
%Dans les deux cas, l'efficacit\'e est un crit\`ere d\'eterminant.% : une donn\'ee qui n'est pas localis\'ee en un temps raisonnable est inutilisable. 
%Le crit\`ere de l'efficacit\'e appliqu\'e aux index est une cons\'equence directe de la taille des r\'eseaux consid\'er\'es.
%Afin de minimiser les co\^uts en termes de bande passante, il est n\'ecessaire que l'acc\`es aux donn\'ees soit con\c cu de telle sorte 
%\`a guider les recherches,  et \`a assurer que si la donn\'ee demand\'ee est index\'ee, elle sera localis\'ee en un temps raisonnable. 
Si les solutions historiques d'index P2P bas\'ees sur des overlays structur\'es 
am\'eliorent effectivement les performances des solutions non-structur\'ees, ce gain est au d\'etriment de la puissance d'expressivit\'e des requ\^etes. 
Typiquement, Chord\cite{stoica01chord} ou CAN\cite{ratnasamy01scalable} ne supportent que les recherches par cl\'e : 
\`a chaque donn\'ee est associ\'e un invariant (obtenue en hachant une cl\'e) et une requ\^ete porte sur un invariant. 
Leur usage est donc confin\'e aux applications qui se suffisent d'une interface de table de hachage.
Les travaux plus r\'ecents s'attachent \`a \'etendre les services des overlays P2P structur\'es aux recherches sur le contenu. 
%l'expressivit\'e des langages de requ\^etes support\'ees afin de en ajoutant des requ\^etes de plus haut niveau, permettant des recherches sur le contenu. 
Les solutions d'index issues de ces travaux sont parfois class\'ees sous l'appellation d'index s\'emantiques. 
  
% Les donn\'ees sont localis\'ees par le biais de descriptions. Plus riches sont les possibilit\'es de description offertes par l'index, 
% plus riches sont les fonctionnalit\'es offertes au service en r\'eseau qui en d\'epend. 
% Un service commun est la recherche par mots cl\'es : prenant en entr\'ee un ensemble de mots cl\'es, l'index localise la ou les donn\'ees dont les descriptions contiennent ces mots cl\'es.
% Si certaines applications peuvent se suffire de recherches par mots cl\'es uniquement, le plus souvent les applications tirent avantage 
% d'une s\'emantique de requ\^etes de plus haut niveau. 

%\paragraph{}
\section*{Probl\`ematiques}
% Nous consid\'erons que la disponibilit\'e d'une infrastructure prenant en charge cette complexit\'e repr\'esente une plus-value 
% certaine dans le d\'eveloppement de larges applications distribu\'ees. 
L'objectif de cette th\`ese est de contribuer au d\'eveloppement de nouvelles m\'ethodes d'acc\`es pour la recherche par contenu 
dans les environnements distribu\'es dynamiques. Nous basons notre solution d'index sur un overlay structur\'e P2P. 
Nous nous focalisons en particulier sur des m\'ethodes destin\'ees \`a la d\'ecouverte de donn\'ees multi-dimensionnelles 
\`a l'aide de requ\^etes par intervalles et de requ\^etes comparatives, incluant les requ\^etes de front de Pareto. 
Nous d\'eveloppons ces points bri\`evement ci-dessous.  


% \section{Probl\'ematique de l'expressivit\'e des requ\^etes}
% 
% Les donn\'ees sont localis\'ees par le biais de descriptions. Plus riches sont les possibilit\'es de description offertes par l'index, 
% plus riches sont les fonctionnalit\'es offertes au service en r\'eseau qui en d\'epend. Un service commun est la recherche par mots cl\'es : prenant en entr\'ee un ensemble de mots cl\'es, l'index localise la ou les donn\'ees dont les descriptions contiennent ces mots cl\'es.
% Si certaines applications peuvent se suffire de recherches par mots cl\'es uniquement, le plus souvent les applications tirent avantage 
% d'une s\'emantique de requ\^etes de plus haut niveau. 
%\paragraph{Requ\^etes par intervalles}
%Parmi les exigences courantes figurent les requ\^etes par intervalles : \'etant donn\'e un champ num\'erique d\'ecrivant les donn\'ees et un intervalle, l'index recherche toutes les donn\'ees dont la valeur de ce champ est comprise dans l'intervalle. 

La premi\`ere probl\'ematique que nous traitons est le \emph{support natif de donn\'ees multi-dimen\-sionnelles}. 
Nous avons vu que les overlays P2P structur\'es r\'esolvent
efficacement les requ\^etes de cl\'e. 
% : \`a chaque donn\'ee est associ\'ee un invariant (cl\'e) et une requ\^ete porte sur un invariant. 
L'indexation par cl\'e revient \`a param\'etrer les donn\'ees par une valeur unique.  
%De mani\`ere g\'en\'erale, les index uni-dimensionnels pr\'evalent dans le domaine des bases de donn\'ees. 
Or une fa\c con commune de repr\'esenter des donn\'ees partag\'ees est 
de les repr\'esenter sous forme de points dans un espace multi-dimensionnel : chaque donn\'ee est caract\'eris\'ee par un nombre fix\'e de valeurs d'attributs, et chaque attribut est 
associ\'e \`a une dimension. 
En prenant l'exemple d'une base de fichiers musicaux, on peut repr\'esenter ces fichiers dans un espace \`a 5 dimensions, chaque dimension correspondant \`a un << tag >> 
ou m\'etadonn\'ee ID3\cite{id3} : titre de la chanson, nom de l'interpr\`ete, nom de l'album, ann\'ee de parution, genre musical.   
Cette repr\'esentation permet d'interroger l'index sur le contenu d'une donn\'ee en formulant des conditions sur ses valeurs d'attributs (titre = << Jolene >> ET date = 1974). 
Le support de requ\^etes par intervalles ou de requ\^etes comparatives implique donc pour un index le support de donn\'ees multi-dimensionnelles. 
Pour que le traitement des requ\^etes multi-dimensionnelles soit efficace, ce support doit de plus \^etre \emph{natif} : l'ensemble des dimensions doit 
\^etre pris en compte simultan\'ement lors de l'indexation et de la localisation. Cette exigence \'ecarte d'embl\'ee les solutions P2P qui r\'eutilisent des index uni-dimensionnels
, que ce soit en juxtaposant de multiples index ou en lin\'earisant l'espace multi-dimensionnel des donn\'ees. 

%L'indexation multi-dimensionnelle a \'et\'e extensivement \'etudi\'ee dans le domaine des bases de donn\'ees centralis\'ees \cite{bertino97indexing,bohm01searching}. 

%Enfin, toute solution de gestion de donn\'ees mutli-dimensionnelles est confront\'ee \`a la \emph{mal\'ediction de la dimension} (<< curse of dimensionality >>). 
% Par exemple, dans une plateforme d'\'echange de fichiers musicaux, chaque fichier peut \^etre rep\'esent\'e par un vecteur d'attributs tels que : 
% son titre, son auteur, son encodage, etc.

La deuxi\`eme probl\'ematique est celle du \emph{support natif des requ\^etes par intervalles}. Une requ\^ete par intervalles 
sp\'ecifie un intervalle de valeurs admises pour un ou plusieurs attributs et recherche l'ensemble des donn\'ees dont les valeurs d'attributs sont comprises dans ces intervalles. 
%recherche l'ensemble des donn\'ees dont la valeur des attributs est comprise dans les intervalles pr\'ecis\'es. 
%Le support de requ\^etes dans les r\'eseaux P2P a \'et\'e identifi\'e comme un probl\`eme de recherche ouvert d'importance par Huebsch et al. \cite{huebsch06querying}. 
Les requ\^etes multi-dimensionnelles par intervalles forment une classe importante de requ\^etes, particuli\`erement utile lorsque 
les valeurs exactes des attributs des donn\'ees recherch\'ees ne sont pas connues \emph{a priori}.
% Dans le cas d'un r\'eseau de capteurs, un exemple de requ\^ete multi-dimensionnelle par intervalles pourrait \^etre : 
% << Rechercher tous les objets tels que ($0 < distance < 50 m$) ET ($vitesse \geq 30 km/h$) >>. 
Or les requ\^etes par intervalles sont intimement li\'ees \`a la notion de \emph{localit\'e} des donn\'ees, c'est-\`a-dire de proximit\'e de ces donn\'ees dans l'espace d'origine. 
D\'ej\`a dans les syst\`emes de bases de donn\'ees, le partitionnement par intervalles des tables dans le but d'optimiser les performances des requ\^etes est un 
probl\`eme bien connu. 
Dans le domaine des index P2P, la localit\'e des donn\'ees est perdue, pour des raisons de performances et de r\'epartition de charge, par les 
solutions d'index bas\'ees sur des overlays structur\'es qui recourent \`a des fonctions de hachage pour distribuer
les donn\'ees sur les n\oe uds (cas de Chord et CAN, mentionn\'es plus haut). 
Des propositions existent, qui visent \`a faire cohabiter application d'une fonction de hachage et localit\'e des donn\'ees multi-dimensionnelles, mais elles 
achoppent sur l'impossibilit\'e de d\'efinir une relation ordre total sur un ensemble de donn\'ees multi-dimensionnelles qui pr\'eserve la localit\'e spatiale.
% Cette classe de solutions, assimilable \`a des tables 
% de hachage distribu\'ees, est impropre \`a la r\'esolution efficace de requ\^etes par intervalles.

%Nous en concluons que pour qu'un index supporte nativement les requ\^etes par intervalles, les m\'ethodes d'acc\`es propos\'ees doivent pr\'eserver un ordre sur les donn\'ees. 

% Or la principale propri\'et\'e m\^eme des DHT, qui est de permettre la r\'epartition de la charge, contrevient \`a cette notion de localit\'e, les rendant impropres \`a la 
% r\'esolution efficace de requ\^etes par intervalles.


Enfin, la troisi\`eme probl\'ematique adress\'ee est celles du \emph{support natif de requ\^etes comparatives}. 
Les types de requ\^etes consid\'er\'es jusqu'ici, que ce soient les requ\^etes par cl\'e ou par intervalles, op\'erent 
une s\'election parmi les donn\'ees en fonction de crit\`eres absolus (en testant les valeurs d'attributs). 
% Nous qualifions ainsi les requ\^etes dont l'objectif est d'op\'erer une s\'election parmi les donn\'ees, non pas en fonction de crit\`eres absolus comme pour des requ\^etes par
% cl\'e ou par intervalles (en testant les valeurs d'attributs). 
Par opposition, les requ\^etes comparatives s\'electionnent les donn\'ees relativement aux autres. 
C'est notamment le cas des requ\^etes de similarit\'e, qui pour une donn\'ee recherchent toutes celles qui lui sont proches selon une fonction distance pr\'e-d\'efinie, 
ou encore les requ\^etes top-$k$, qui recherchent les $k$ donn\'ees les plus optimales pour une fonction d'utilit\'e pr\'e-d\'efinie. 
En donnant une information sur la composition de l'ensemble des donn\'ees, les requ\^etes comparatives constituent des outils pr\'ecieux d'aide \`a la d\'ecision multi-crit\`eres. 
% De plus, elles 
% permettent de g\'erer l'inflation des donn\'ees en permettant de limiter aux donn\'ees les plus pertinentes le nombre de r\'eponses retourn\'ees. 
Dans cette dissertation, nous nous int\'eressons plus particuli\`erement aux requ\^etes comparatives de type << front de Pareto >>, aussi appel\'ees \emph{requ\^etes skyline}. 
Une requ\^ete skyline recherche dans un ensemble les donn\'ees qui ne sont \emph{domin\'ees} par aucune autre. En supposant un probl\`eme de maximisation, 
une donn\'ee en domine une autre si en prenant leurs valeurs d'attributs deux \`a deux, elle est sup\'erieure ou \'egale pour toutes les dimensions, et si pour au moins une dimension 
elle est strictement sup\'erieure. 
Informellement, cela revient \`a consid\'erer qu'\`a chaque dimension est associ\'ee une fonction d'utilit\'e monotone et qu'une donn\'ee appartient au front de Pareto 
si elle est pr\'ef\'erable selon toutes les fonctions d'utilit\'e \`a toutes les autres donn\'ees. 
%Un exemple de requ\^etes skyline est : << Rechercher les morceaux les plus r\'ecents les plus t\'el\'echarg\'es >>.
Les requ\^etes skyline ont \'et\'e \'etudi\'ees extensivement dans les syst\`emes centralis\'es et font l'objet de recherches en bases de donn\'ees depuis \cite{borzsonyi01skyline}. 
Les algorithmes d\'evelopp\'es sont difficilement transposables au contexte d\'ecentralis\'e des index P2P, ce qui explique peut \^etre le peu de contributions dans le domaine.
Parmi les quelques travaux employant des overlays structur\'es, \cite{wu06parallelizing} contraint la recherche des donn\'ees dominantes \`a une r\'egion de l'espace des
donn\'ees. Tandis que \cite{chen08isky, wang08intelligent} construisent leur solution sur un index uni-dimensionnel,
ce qui n\'ecessite de r\'eduire la dimensionalit\'e des donn\'ees originelles et provoque une perte de la localit\'e n\'efaste au support natif des requ\^etes par intervalles. 

%Nous en concluons que pour qu'un index supporte nativement les requ\^etes par intervalles, les m\'ethodes d'acc\`es propos\'ees doivent pr\'eserver un ordre sur les donn\'ees. 


% Parmi les applications qui typiquement ne se suffisent pas de recherche par mots cl\'es figurent les applications qui ont une approche 
% exploratoire des donn\'ees. Les requ\^etes par mot cl\'es suppose une connaissance a priori des mots cl\'es. 
% L'exploration de donn\'ees n\'ecessite des requ\^etes comparatives qui informent non pas sur l'existence dans 
% l'absolu d'une donn\'ees mais sur la composition de l'ensemble des donn\'ees.   

%C'est l\`a qu'intervient l'index. 

% Le r\^ole de l'index consiste, dans une syst\`eme au sein duquel les donn\'ees/connaissances/ressources sont en grand nombre
% % et distribu\'ees sur un ensemble de sites,
% , \`a fournir au syst\`eme et/ou \`a ses utilisateurs des outils de recherche efficaces et adapt\'es. 

%Dans le cas qui nous int\'eresse, les donn\'ees, en plus d'\^etre en grand nombre, sont r\'eparties g\'eographiquement. 
% La probl\'ematique peut \^etre formul\'ee de la mani\`ere suivante : Etant donn\'e un ensemble de machine en r\'eseau/pouvant communiquer entre elles, 
% et un ensemble de donn\'ees distribu\'ees sur ces machines, comment trouver une ressource donn\'ee dont on poss\`ede la description ? 

% Exemples : 
% \begin{itemize}
% %	\item Pour une applications Web : stockage d'\'etats transients type << paniers >> du site commercial Amazon
% 	\item Pour une plateforme musicale : localisation de fichiers 
% 	\item Pour une grille informatique, localisation de ressources machine 
% 	\item Pour une application d'informatique ambiante : d\'ecouverte de services, g\'eolocalisation
% \end{itemize}
% \vspace{0.6cm}
% 
% L'argument de l'efficacit\'e est pr\'ecis\'e car dans le contexte dans lequel nous nous sommes plac\'es, il n'est pas envisageable 
% d'effectuer des recherches par force brute. Pour cette raison la conception de l'index doit int\`egrer le passage \`a 
% l'\'echelle, du moins en termes de donn\'ees : l'ajout de donn\'ees au syst\`eme ne doit pas augmenter proportionnellement la complexit\'e des des t\^aches d'indexation 
% et de localisation. 

%\section{Probl\'ematique sp\'ecifique}

%Nous nous int\'eressons donc aux index d\'ecentralisa\'es expressifs. 

%Pour r\'epondre aux besoins exprim\'es ci-dessus, un syst\`eme d'indexation et de localisation, ou \emph{index} devrait satisfaire trois principaux objectifs : (i) g\'erer des donn\'ees
%multi-dimensionnelles, (ii) g\'erer des requ\^etes expressives, (iii) 

%Les propri\'et\'es des applications d\'ecentralis\'ees de type P2P ont une incidence sur la conception d'index 
%
%En tant que brique logicielle de syst\`emes distribu\'es, nous nous int\'eressons \`a des index distribu\'es. Nous imposons que les donn\'ees et les traitement soient totalement d\'ecentralis\'es afin de pouvoir d'int\'egrer \`a des syst\`emes en l'absence de toute connaissance globales (syst\`emes P2P, informatique pervasive, etc.). 
%
%Parmi les crit\`eres d'\'evaluation d'un index, nous avons choisi de contribuer \`a leur expressivit\'e. Nous d\'esignons par expressivit\'e 
%d'un index sa capacit\'e \`a traiter diff\'erents types de requ\^etes. 
%%Si dans le domaine des index comme dans les autres domaines de 
%%l'informatique, il ne peut y avoir de << couteau suisse >> ou de solution universelle, il est tout de m\^eme souhaitable qu'un index permette 
 
% \paragraph{}Un cas d'\'etude inspir\'e d'une plateforme musicale r\'eelle, Jamendo, est propos\'e afin d'illustrer les enjeux li\'es \`a l'expressivit\'e des 
% requ\^etes dns un index. 
% 
% Les plateformes de t\'el\'echargement de musique classique tels que eMule\cite{emule}, eDonkey\cite{edonkey} ou Pirate Bay \cite{piratebay} peuvent 
% 
% % \paragraph{Cas d'\'etude : Une plateforme de d\'ecouverte musicale}
% % % Les plateformes P2P de t\'el\'echargement de fichiers multim\'edia constituent sans doute un des services en r\'eseau \`a l'\'echelle d'Internet le plus populaire. 
% % % Contrairement \`a leurs pr\'edecesseurs Napster ou AudioGalaxy, qui centralisaient le traitement des requ\^etes, ces applications d\'ecentralisent 
% % % \`a la fois les traitements et les donn\'ees.   
% % L'objectif d une plateforme de t\'el\'echargement de fichiers musicaux\footnote{On se place dans le cas de fichiers sous licence de type Creative Commons}, on a vu, 
% % est de permettre \`a chaque utilisateur de mettre \`a disposition de la communaut\'e des morceaux de musique qu'il poss\`ede et/ou d'acc\'eder \`a de nouveaux morceaux. 
% % Pour des raisons de co\`ut de stockage, d'administration et de confidentialit\'e des donn\'ees 
% % la gestion des donn\'ees et des m\'etadonn\'ees est effectu\'ee \emph{in situ}. 
% %eMule\cite{emule}, eDonkey\cite{edonkey}, Pirate Bay \cite{piratebay}, etc. 
% %Ces outils sont tr\`es utiles et peuvent se pr\'evaloir d'un large choix et de bonnes performances. 
% Toutefois, ils sont d\'edi\'es \`a la recherche de morceaux pr\'ecis et en tant que tels, 
% ne proposent que des recherches par mots clefs. Sous eMule par exemple, l'interface de recherche d'un fichier se limite \'a deux champs texte : "nom" et "type". 
% 
% Par opposition, le cr\'eneau des plateformes de t\'el\'echargement telles que Jamendo \cite{jamendo} ou DogMazik \cite{dogmazic}
%  est la \emph{d\'ecouverte} de nouveaux artistes. Aux artistes n'ayant pas (encore) de maison de production, ces plateformes offrent un outil diffusion et de 
% r\'ef\'erencement sur Internet, et donc leur permet d'augmenter leur visibilit\'e. Au public, ces plateformes offrent un outil de d\'ecouverte d'artistes \'emergents. 
% Dans la suite, nous distinguons parmi les deux types de plateforme : classique ou de d\'ecouverte. 
% Les plateformes de d\'ecouverte proposent des fonctionnalit\'es de recherche plus \'evolu\'ees que les plateformes classiques. En effet, l'aspect exploratoire de ces plateformes 
% de d\'ecouverte suppose des crit\`eres de recherche ne se r\'eduisant pas aux seuls mots cl\'es. 
% Puisque le titre ou l'auteur des morceaux propos\'es \`a la d\'ecouverte est suppos\'e inconnu au client de la plateforme, 
% d'autres crit\'eres de choix doivent \^etre propos\'es : recherche par genre musical, par p\'eriode, par popularit\'e, ... Ainsi, si l'on prend l'exemple de 
% Jamendo, qui est la premi\`ere plateforme mondiale de t\'el\'echargement de morceaux de musique gratuits et l\'egaux (18 000 albums soit env. 180 000 titres)
% %\footnote{Hypoth\`ese : on consid\`ere dans ce qui suit que les donn\'ees manipul\'ees sont les *titres* et non les albums ou les artistes}
% , un morceau est publi\'e par un artiste avec des m\'etadonn\'ees : titre de la chanson, nom de l'interpr\`ete, nom de l'album, ann\'ee de parution, genre musical, etc.  
% La description est ensuite enrichie par des attributs dynamiques, qui vont servir de m\'etriques de 
% popularit\'e, tels que : nombre d'\'ecoutes, nombre de t\'el\'echargements, nombre de fois o\`u il a \'et\'e d\'eclar\'e << favori >>, nombre de << playlist >> 
% cr\'e\'ees le contenant, nombre de liens le r\'ef\'eren\c cant, etc. Les types de recherche permis sont alors : 
% recherche de top-k selon la popularit\'e (par ex. les 100 titres les plus \'ecout\'es), selon la 
% popularit\'e mensuelle, la popularit\'e hebdomadaire, les derni\`eres sorties, les plus t\'el\'echarg\'es, les plus \'ecout\'es, les plus playlist\'es. 

%A synth\'etiser dans intro ? A deplacer dans future work ? 

%
%Le dernier exemple que nous proposerons ici est celui d'index d\'ecentralis\'e pour allocateur de ressources dans une grille informatique. 
%En tant qu'environnement de partage de ressources mat\'erielles et logicielles, l'allocateur d'une grille informatique repose de mani\`ere critique sur le service de 
%localisation et la d\'ecouverte de ressources \cite{iamnitchi03grid}. 
%Etant donn\'ees la description des ressources d\'esir\'ees (en termes d'espace disque, CPU, version du syst\`eme d'exploitation, etc.), 
%l'allocateur renvoie la localisation des ressources satisfaisant cette description. La conception d'un allocateur qui soit adapt\'e \`a un environnement de 
%grille h\'et\'erog\`ene, dynamique, \`a large \'echelle est non triviale et les solutions centralis\'ees traditionnelles (typiquement Globus \cite{foster97globus}) 
%ont montr\'e leurs limites \cite{iamnitchi04peer}. Face \`a ces enjeux, de nom breux auteurs \cite{foster03ondeath, talia03toward, trunfio07peer} ont soulign\'e l'int\'er\^et 
%d'une approche P2P pour la conception d'allocateurs de grille d\'ecentralis\'es. %ad\'equation entre les besoins de conception d'un allocateur de grille et les propri\'et\'es du paradigme P2P. 
%Par-ailleurs, la r\'esolution de requ\^etes par intervalles sur des donn\'ees multi-dimensionnelles est un point clef dans de nombreux scenarii d'utilisation de grille. 
%Partant de ce double constat, de nombreux travaux ont propos\'e sp\'ecifiquement des solutions d'allocateur P2P g\'erant les requ\^etes par intervalles 
%\cite{andrzejak02scalable, iamnitchi02peer, spence03xenosearch, cai04maan}. En tant qu'overlay P2P dot\'e d'une s\'emantique de requ\^etes incluant les requ\^etes par intervalles, 
%notre solution offre de nombreux atouts pour la r\'ealisation d'un tel allocateur. Le chapitre de l'\'etat de l'art d\'emontre explicitement la sup\'eriorit\'e de PBAM sur 
%certaines d'entre elles \ref{maan}.

\section*{Contributions}

% Les pr\'emices de cette introduction ont exhib\'e les besoins sp\'ecifiques en termes de m\'ethodes d'acc\`es d\'ecentralis\'ees 
% des syst\`emes distribu\'es dynamiques dont les donn\'ees sont g\'er\'ees \emph{in situ}. 

%C'est dans ce cadre que nous proposons une solution d'index bas\'ee sur un overlay P2P. 
La contribution de cette th\`ese est : une solution d'index bas\'ee sur un overlay P2P. 
En particulier, nous nous emparons des probl\'ematiques li\'ees aux recherches sur le contenu dans les overlays structur\'es et 
proposons un support natif des requ\^etes multi-dimensionnelles par intervalles et comparatives, dont les requ\^etes skyline. 

Tout d'abord, nous fournissons un \'etat de l'art du domaine. Apr\`es un survol de diff\'erentes approches de la gestion de donn\'ees dans les syst\`emes distribu\'es, 
nous abordons l'approche P2P en nous concentrant sur les solutions structur\'ees et semi-structur\'ees. Dans la discussion qui suit, nous 
distinguons les diff\'erentes \'etapes de conception d'un index P2P structur\'e g\'en\'erique, 
%distinguons les solutions selon qu'elles sont dirig\'ees par le routage ou par les donn\'ees, 
ce qui nous permet de mettre en \'evidence l'\'eventail des techniques utilis\'ees, ainsi que leurs tenants et aboutissants. 
Nous nous attardons sur les solutions qui pr\'esentent le plus de similarit\'es avec la notre, \`a savoir les solutions 
distribuant sur les pairs une structure de type arborescente. 

Notre seconde contribution est un mod\`ele complet d'index nomm\'e PosNet, dont les propri\'et\'es sont les suivantes. 
PosNet supporte nativement un mod\`ele de donn\'ees multi-dimensionnel, chaque dimension \'etant associ\'ee \`a un ordre total (soit une fonction d'utilit\'e monotone). 
PosNet est totalement d\'ecentralis\'e : aucune t\^ache ne n\'ecessite la connaissance globale de l'\'etat du syst\`eme. 
PosNet est auto-organisant : la distribution des donn\'ees sur les n\oe uds de l'overlay est dynamique et pr\'eserve la continuit\'e du service de localisation. 
% Que ce soit pour l'indexation et la localisation efficace de donn\'ees, ou bien pour la mise-\`a-jour de l'overlay, les n\oe uds de PosNet
% ne  qu'une connaissance uniquement locale de l'\'etat du syst\`eme. 
%Les types de requ\^etes support\'ees incluent les requ\^etes exactes, incompl\`etes, par intervalles et skyline. 
% PosNet est bas\'e sur une relation d'ordre produit. Il supporte nativement l'indexation et la localisation
% de donn\'ees multidimensionnelles. 
PosNet supporte nativement un mod\`ele de requ\^ete riche. Soit $E$, un ensemble de donn\'ees index\'ees de dimension $n$, % et admettant un ordre produit $\preccurlyeq$, 
et $d_1=(a_{11},\ldots,a_{1n}) \text{ et } d_2=(a_{21},\ldots,a_{2n})$, deux donn\'ees dans $E$, PosNet permet de r\'epondre entre autres aux requ\^etes suivantes :  
\begin{itemize}
\item $d_1$ est il contenu dans $E$ (requ\^ete exacte) ? 
%\item Quel est l'ensemble des donn\'ees $d$ de $E$ comprises entre $d_1$ et $d_2$ (requ\^etes par plages de valeur) ?
\item Etant donn\'es les intervalles de valeurs $[x_j,y_j]$ et $[x_k,y_k]$ pour les dimensions $j$ et $k$, quelles sont les donn\'ees $d_i$ de $E$ telles que 
%$(bi_{ij}<a_{ij}<bs_{ij})$ et $(bi_{ik}<a_{ik}<bs_{ik})$ (requ\^etes par intervalles) ?
$(x_j<a_{ij}<y_j)$ et $(x_k<a_{ik}<y_k)$ (requ\^etes par intervalles) ?    
\item Quelles sont les donn\'ees $d_i$ de $E$ telles que $a_{ij}=x$ (requ\^ete incompl\`ete) ? 
\item Quel est le front de Pareto de l'ensemble $E$ (requ\^ete skyline) ?
%\item Quel est l'ensemble des donn\'ees qui contient $d_1$ (sur-ensemble) ? 
%\item Quel est l'ensemble des donn\'ees qui est contenu par $d_2$ (sous-ensemble) ? 
\end{itemize}
%Supposant une repr\'esentation des donn\'ees sous forme de tuples
Pour obtenir ces propri\'et\'es, nous proposons d'abord une structure de donn\'ees multi-dimension\-nelle de type graphe, appel\'ee \emph{graphe s\'emantique}, 
dont l'originalit\'e r\'eside dans l'exploitatoin d'une relation d'ordre partiel d\'efinie sur les donn\'ees.
Ensuite, nous proposons une famille d'algorithmes de recherche dans le graphe s\'emantique, pour la r\'esolution des requ\^etes par intervalles et de comparaison. 
L'efficacit\'e de ces algorithmes tient d'une part \`a une recherche simultan\'ee sur l'ensemble des dimensions, qui \'evite le surco\^ut associ\'e aux m\'ethodes
d'agr\'egation de r\'esultats partiels.  
D'autre part \`a une minimisation du nombre de comparaisons n\'ecessaires \`a la r\'esolution d'une requ\^ete, par \'elagage de l'espace de recherche. 
Enfin, le verrou technologique majeur que soul\`eve l'exploitation d\'ecentralis\'ee du graphe s\'emantique est sa distribution sur un r\'eseau P2P. 
Nous proposons donc les protocoles (i) de placement des donn\'ees sur les n\oe uds d'un overlay, (ii) de routage des requ\^etes dans cet
overlay et (iii) de gestion de la dynamicit\'e de l'overlay (arriv\'ee ou d\'epart d'un pair). 


%INSERER ICI DES RESULTATS CHIFFRES CONCERNANT LES PERFS
% Expliquer les difficult\'es r\'esolues : gestion native de donn\'ees multidimensionnelles pour le passage \`a l'\'echelle en termes de dimensionnalit\'e 
% (=> on s'interdit les approches de type \ ``join'') / gestion de requ\^etes non g\'er\'ees dans l'existant, m\^eme dans le domaine de la BD / gestion de la d\'ecentralisation de 
% l'index / conception d'algorithmes de recherche minimisant le nombre de comparaisons (cf. Levinson)

% Les concepts introduits : 
% \begin{itemize}
% \item Une formulation du probl\`eme g\'en\'eral de la localisation de donn\'ees multidimensionnelles \`a l'aide de requ\^etes comparatives
% \item Une expressivit\'e des recherches accrue par rapport \`a l'existant, gr\^ace \`a une structure de donn\'ees innovante de type graphe, 
% permettant d'exploiter un ordre partiel sur les donn\'ees
% \item De nouveaux algorithmes de parcours de ce graphe de similarit\'e permettant de guider la recherche sur la base de connaissances locales, 
% exploitables dans une architecture d\'ecentralis\'ee
% \item Les r\'esultats obtenus : un mod\`ele, un proto, des \'evals
% \item La mani\`ere de les obtenir
% \end{itemize}

%%\section{Contributions} \label{contributions}
%% 
%% \begin{itemize}
%%   \item Ce que je reprends : 
%% \begin{itemize}
%%  \item Le paradigme P2P pour le passage \`a l'\'echelle, l'auto-organisation : 
%% Le premier crit\`ere de passage \`a l'\'echelle d\'ecourage d'office le choix
%% d'une solution centralis\'ee. En effet, un point central en plus de constituer
%% un goulet d'\'etranglement et un \emph{single point of failure, }implique
%% un \'etat en $O (N)$ (avec N le nombre de pairs)
%% \item Un overlay s\'emantique pour l'expressivit\'e, et semi-structur\'e pour la compl\'etude ;
%% \end{itemize}
% 
%%   \item Ce que j'apporte : PosNet un nouvel index P2P s\'emantique
%%   semi-structur\'e fond\'e sur une structure de donn\'ees originale
%%   d\'esign\'ee par   graphe s\'emantique  :
%%   \begin{itemize}
%%     \item Permettant d'indexer   nativement  MAL DIT ?] les ressources
%%     multidimensionnelles, m\^eme partiellement d\'efinies ;
%%     
%%     \item Structurant l'espace de description pour une recherche efficace :
%%     \begin{itemize}
%%       \item Pr\'eservant la localit\'e s\'emantique, afin d'optimiser les
%%       requ\^etes par plages de valeurs ;
%%       
%%       \item Exprimant un ordre sur les ressources, afin d'optimiser les
%%       requ\^etes comparatives et de garantir la compl\'etude de la recherche ;
%%       
%%       \item Dont les propri\'et\'es structurelles permettent de g\'erer les
%%       requ\^etes partielles.
%%     \end{itemize}
%%   \end{itemize}
%%   Le verrou technologique majeur que soul\`eve l'exploitation du graphe
%%   s\'emantique dans un overlay P2P est sa distribution, sa maintenance et son
%%   utilisation de mani\`ere totalement d\'ecentralis\'ee. La suite du document
%%   d\'ecrit le graphe s\'emantique (chapitre ???) et la mani\`ere dont on a
%%   lev\'e ce verrou dans PosNet : [reste du PLAN].
%% \end{itemize}
Enfin notre troisi\`eme contribution est une impl\'ementation distribu\'ee de PosNet en Python, nomm\'ee Pyposnet, et dont le code est disponible en Google Code \cite{pyposnet} 
(source ouverte). 

\section*{Plan de la dissertation}
Le reste de la dissertation est organis\'e comme suit. Le chapitre \ref{chap:Indexation et localisation dans les syst\`emes distribu\'es \`a grande \'echelle} 
\'elabore une grille d'\'evaluation des solutions d'index au regard de nos objectifs, qui permet d'orienter l'\'etude des solutions d'index distribu\'ees qui s'en suit. 
La mise en \'evidence \`a ce chapitre des limitations de l'existant permet au chapitre \ref{chap:Probl\'ematiques et pr\'esentation g\'en\'erale de PosNet} 
suivant de circonscrire les probl\'ematiques sp\'ecifiques de cette dissertation et 
de pr\'esenter une vue g\'en\'erale de la solution que nous y apportons. Les d\'etails du fonctionnement de la solution sont donn\'es aux 
chapitres \ref{chap:Plan de transfert des requ\^etes}, qui porte sur
les m\'ecanismes de recherche et \ref{chap:Plan de contr\^ol}, qui \'eclaire les m\'ecanismes de mise-en-place et de maintien de l'index. 
Enfin le chapitre \ref{chap:Conclusion et Perspectives} apporte une conclusion et discute des directions de recherche futures. 


